{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Superposition Kata Workbook\n",
    "\n",
    "**What is this workbook?**\n",
    "A workbook is a collection of problems, accompanied by solutions to them. \n",
    "The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required. \n",
    "\n",
    "Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.\n",
    "\n",
    "This workbook describes the solutions to the problems offered in the [Superposition kata](./Superposition.ipynb). \n",
    "Since the tasks are offered as programming problems, the explanations also cover some elements of Q# that might be non-obvious for a first-time user.\n",
    "\n",
    "**What you should know for this workbook**\n",
    "\n",
    "You should be familiar with the following concepts before tackling the Superposition kata (and this workbook):\n",
    "1. Basic linear algebra\n",
    "2. The concept of qubit and multi-qubit systems\n",
    "3. Single-qubit and multi-qubit quantum gates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To begin, first prepare this notebook for execution (if you skip this step, you'll get \"Syntax does not match any known patterns\" error when you try to execute Q# code in the next cells):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%package Microsoft.Quantum.Katas::0.10.1911.1607"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The package versions in the output of the cell above should always match. If you are running the Notebooks locally and the versions do not match, please install the IQ# version that matches the version of the `Microsoft.Quantum.Katas` package.\n",
    "> <details>\n",
    "> <summary><u>How to install the right IQ# version</u></summary>\n",
    "> For example, if the version of `Microsoft.Quantum.Katas` package above is 0.1.2.3, the installation steps are as follows:\n",
    ">\n",
    "> 1. Stop the kernel.\n",
    "> 2. Uninstall the existing version of IQ#:\n",
    ">        dotnet tool uninstall microsoft.quantum.iqsharp -g\n",
    "> 3. Install the matching version:\n",
    ">        dotnet tool install microsoft.quantum.iqsharp -g --version 0.1.2.3\n",
    "> 4. Reinstall the kernel:\n",
    ">        dotnet iqsharp install\n",
    "> 5. Restart the Notebook.\n",
    "> </details>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"plus-state\"></a> Task 1. Plus state.\n",
    "\n",
    "**Input:** A qubit in the $|0\\rangle$ state.\n",
    "\n",
    "**Goal:**  Change the state of the qubit to $|+\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + |1\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "Look up any list of quantum gates, for example, [Quantum logic gate @ Wikipedia](https://en.wikipedia.org/wiki/Quantum_gate). Typically one of the first gates described will be the [Hadamard gate](https://en.wikipedia.org/wiki/Quantum_logic_gate#Hadamard_(H)_gate): \n",
    "\n",
    "$$H = \\frac{1}{\\sqrt2} \\begin{bmatrix} 1 & 1 \\\\ 1 & -1 \\end{bmatrix}$$\n",
    "\n",
    "This gate converts $|0\\rangle$ into $|+\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle + |1\\rangle\\big)$ and $|1\\rangle$ into $|−\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle - |1\\rangle\\big)$.  The first of these transformations is exactly the one we're looking for!\n",
    "\n",
    "To implement this operation in Q#, look at the list of [intrinsic gates](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic) available in Q#. \n",
    "[Hadamard gate](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.h) is one of them. \n",
    "`Microsoft.Quantum.Intrinsic` namespace is open in Notebooks by default, so you can use the gates in the code right away. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T01_PlusState_Test \n",
    "\n",
    "operation PlusState (q : Qubit) : Unit {\n",
    "    H(q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 1 of the Superposition kata.](./Superposition.ipynb#plus-state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"minus-state\"></a> Task 2. Minus State.\n",
    "\n",
    "**Input:** A qubit in the $|0\\rangle$ state.\n",
    "\n",
    "**Goal:**  Change the state of the qubit to $|-\\rangle = \\frac{1}{\\sqrt{2}} \\big(|0\\rangle - |1\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "As we've seen in the previous task, the Hadamard gate maps the basis state $|0\\rangle$ to $\\frac{1}{\\sqrt2}\\big(|0\\rangle + |1\\rangle\\big)$ and $|1\\rangle$ to $\\frac{1}{\\sqrt2}\\big(|0\\rangle - |1\\rangle\\big)$. \n",
    "If our qubit was already in the $|1\\rangle$ state, we would simply apply the Hadamard gate to prepare the required $|-\\rangle$ state. \n",
    "However, there is another operation we can use to change the state $|0\\rangle$ to $|1\\rangle$, namely the [X gate](https://en.wikipedia.org/wiki/Quantum_logic_gate#Pauli-X_gate):\n",
    "\n",
    "$$X = \\begin{bmatrix} 0 & 1 \\\\ 1 & 0 \\end{bmatrix}$$\n",
    "\n",
    "This gate transforms $|0\\rangle \\longmapsto |1\\rangle$ and $|1\\rangle \\longmapsto |0\\rangle$.\n",
    "\n",
    "Here is the sequence of the steps to arrive to the solution:\n",
    "\n",
    "<table style=\"background-color: white; border:1px solid; tr  { background-color:transparent; }\">\n",
    "    <col width=400>\n",
    "    <col width=300>\n",
    "    <col width=300>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Description of operation</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Notation</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Circuit</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:left; border:1px solid\">Apply the X gate to $|0\\rangle$ to get $|1\\rangle$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$X|0\\rangle = |1\\rangle$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/testcircuit.png\"/></td>    \n",
    "      </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:left; border:1px solid\">Apply the Hadamard gate to $|1\\rangle$ to get $\\frac{1}{\\sqrt2}\\big(|0\\rangle - |1\\rangle\\big)$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\">$H|1\\rangle = \\frac{1}{\\sqrt2}\\big(|0\\rangle - |1\\rangle\\big)$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/singlehadamard.png\"/></td>       \n",
    "    </tr>   \n",
    "</table>\n",
    "\n",
    "In Q#, each gate is applied to the qubit sequentially, transforming its internal state. [X gate](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.x) is another gate in the `Microsoft.Quantum.Intrinsic` namespace."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T02_MinusState_Test \n",
    "\n",
    "operation MinusState (q : Qubit) : Unit {\n",
    "    X(q);\n",
    "    H(q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 2 of the Superposition kata.](./Superposition.ipynb#minus-state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"unequal-superposition\"></a>  Task 3. Unequal superposition.\n",
    "\n",
    "**Input:** \n",
    "\n",
    "1. A qubit in the $|0\\rangle$ state.\n",
    "2. Angle $\\alpha$, in radians, represented as `Double`.\n",
    "\n",
    "**Goal:**  Change the state of the qubit to $\\cos\\alpha|0\\rangle$ + $\\sin\\alpha|1\\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "<table style=\"background-color: white; border:0 solid; tr  { background-color:white; }\">\n",
    "    <col width=130>\n",
    "    <col width=300>\n",
    "    <col width=130>\n",
    "    <col width=230>\n",
    "        <td style=\"text-align:center; font-bold; font-size: 14px; background-color:white; border:0\">We want to move from the starting state</td>\n",
    "        <td style=\"text-align:center; background-color:white; border:0\"><img src=\"./img/Task3UnitcircleStart.png\"/></td>\n",
    "        <td style=\"text-align:center; font-bold; font-size: 14px; background-color:white; border:0\">To the desired final state</td>\n",
    "        <td style=\"text-align:center; background-color:white; border:0\"><img src=\"./img/Task3UnitcircleFinal.png\"/></td>       \n",
    "       </tr>\n",
    " </table>\n",
    "In other words, we are looking for some kind of a rotation operation. There are three special gates that implement rotations around various axis of the Bloch Sphere: \n",
    "\n",
    "<table style=\"background-color: white; border:0 solid; tr  { background-color:white; }\">\n",
    "    <col width=300>\n",
    "    <col width=300>\n",
    "    <col width=250>\n",
    "    <tr>\n",
    "        <td style=\"text-align:left; font-size: 14px; background-color:white; border:0\">$R_x(\\theta) = \\begin{bmatrix} \\cos\\frac{\\theta}{2} & -i\\sin\\frac{\\theta}{2} \\\\ -i\\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2} \\end{bmatrix}$</td>\n",
    "        <td style=\"text-align:left; font-size: 14px; background-color:white; border:0\">$R_y(\\theta) = \\begin{bmatrix} \\cos\\frac{\\theta}{2} & -\\sin\\frac{\\theta}{2} \\\\ \\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2} \\end{bmatrix}$</td>\n",
    "        <td style=\"text-align:left; font-size: 14px; background-color:white; border:0\">$R_z(\\theta) = \\begin{bmatrix} e^{-i\\theta/2} & 0 \\\\ 0 & e^{i\\theta/2} \\end{bmatrix}$</td>\n",
    "      </tr>    \n",
    "</table>\n",
    "\n",
    "If we were to apply the $R_x$ gate to a qubit in the $|0\\rangle$ state, we would introduce complex coefficients to the amplitudes, which is clearly not what we're looking for. Similarly, the $R_z$ gate introduces only a global phase when applied to $|0\\rangle$ state, so we can rule it out as well. This leaves only the $R_y$ as a starting point for the solution.\n",
    "\n",
    "Applying the $R_y$ gate to the $|0\\rangle$ state, we get:\n",
    "$$R_y(\\theta) |0\\rangle = \\begin{bmatrix} \\cos\\frac{\\theta}{2} & -\\sin\\frac{\\theta}{2} \\\\ \\sin\\frac{\\theta}{2} & \\cos\\frac{\\theta}{2} \\end{bmatrix} \\begin{bmatrix} 1 \\\\ 0 \\end{bmatrix} = \\begin{bmatrix} \\cos\\frac{\\theta}{2} \\\\ \\sin\\frac{\\theta}{2} \\end{bmatrix} = \\cos\\frac{\\theta}{2}|0\\rangle + \\sin\\frac{\\theta}{2}|1\\rangle$$\n",
    "\n",
    "Therefore, applying the $R_y(2\\alpha$) gate to $|0\\rangle$ is the solution to our problem. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> <table style=\"background-color: white; font-size: 14px; border:0 solid; tr  { background-color:white; }\">\n",
    "    <col width=600>\n",
    "    <col width=300>\n",
    "    <tr>\n",
    "        <td style=\"text-align:left; background-color:white; border:0\">\n",
    "Let us have a look at the Bloch sphere to obtain a geometrical interpretation of the operation.\n",
    "<br/><br/>\n",
    "The X-Z plane has no complex numbers, i.e. for qubit states that fall on it the amplitudes for both $|0\\rangle$ and $|1\\rangle$ basis states will always be real. We can see that the $R_y$ gate, which rotates the qubit state around the Y axis, keeps it within the X-Z plane. \n",
    "<br/><br/> \n",
    "Looking at the other two gates, $R_x$ gate rotates the qubit state around the X axis and thus takes the qubit state out of the X-Z plane, introducing complex coefficients. $R_z$ gate rotates the qubit state around the Z axis, so it doesn't modify the $|0\\rangle$ state which lies on the Z axis.\n",
    "<br/><br/> \n",
    "In case you are surprised to see the $|0\\rangle$ and $|1\\rangle$ vectors 180 degrees apart from each other, the Bloch sphere represents orthogonal vectors as opposite points on the sphere.  \n",
    "You can learn more about the bloch sphere from <a href=\"http://www.vcpc.univie.ac.at/~ian/hotlist/qc/talks/bloch-sphere.pdf\">this presentation</a></td>\n",
    "        <td style=\"text-align:center; font-size: 14px; background-color:white; border:0\"><img src=\"./img/blochsphere.png\"/></td> \n",
    "      </tr>    \n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Q#, $R_y$ gate is represented as [Ry](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry) operation. Note that you have to apply $R_y(2\\alpha)$, not $R_y(\\alpha)$; Q# does not have implicit type casing from `Int` to `Double`, so you have to calculate the angle parameter of the operation as `2.0 * alpha`, using a double constant 2.0 instead of an integer 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T03_UnequalSuperposition_Test \n",
    "\n",
    "operation UnequalSuperposition (q : Qubit, alpha : Double) : Unit {\n",
    "    Ry(2.0 * alpha, q);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 3 of the Superposition kata.](./Superposition.ipynb#unequal-superposition)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"superposition-of-all-basis-vectors-on-two-qubits\"></a>Task 4. Superposition of all basis vectors on two qubits.\n",
    "\n",
    "**Input:** Two qubits in the $|00\\rangle$ state (stored in an array of length 2).\n",
    "\n",
    "**Goal:** Change the state of the qubits to $|+\\rangle \\otimes |+\\rangle = \\frac{1}{2} \\big(|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We know that the Hadamard gate maps the basis state $|0\\rangle$ to $\\frac{1}{\\sqrt2}(|0\\rangle + |1\\rangle)$, so it is a logical starting point for solving this problem. \n",
    "\n",
    "Next, we see that the final state has a $\\frac{1}{2}$ term hinting that we might be applying two operations involving a $\\frac{1}{\\sqrt{2}}$ term. \n",
    "\n",
    "Now, how do we get the $|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle$ expression? Let's see what does multiplying the expression $|0\\rangle + |1\\rangle$ by itself look like:\n",
    "\n",
    "$$\\big(|0\\rangle + |1\\rangle\\big) \\otimes \\big(|0\\rangle + |1\\rangle\\big) = |0\\rangle|0\\rangle + |0\\rangle|1\\rangle + |1\\rangle|0\\rangle + |1\\rangle|1\\rangle = \\\\\n",
    "= |00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle$$\n",
    "\n",
    "Thus, applying the Hadamard gate to each qubit in isolation will deliver the desired final result:\n",
    "\n",
    "$$H|0\\rangle \\otimes H|0\\rangle = \\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big) \\otimes \\frac{1}{\\sqrt2}\\big(|0\\rangle + |1\\rangle\\big) = \\\\\n",
    "= \\frac{1}{2} (|00\\rangle + |01\\rangle + |10\\rangle + |11\\rangle)$$\n",
    "\n",
    "Q# arrays are similar to arrays in other languages: you can access the $i$-th element of the array `qs` as `qs[i]` (indices are 0-based)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T04_AllBasisVectors_TwoQubits_Test\n",
    "\n",
    "operation AllBasisVectors_TwoQubits (qs : Qubit[]) : Unit {\n",
    "    H(qs[0]);\n",
    "    H(qs[1]);   \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 4 of the Superposition kata.](./Superposition.ipynb#superposition-of-all-basis-vectors-on-two-qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"superposition-of-basis-vectors-with-phases\"></a>Task 5. Superposition of basis vectors with phases.\n",
    "\n",
    "**Input:** Two qubits in the $|00\\rangle$ state (stored in an array of length 2).\n",
    "\n",
    "**Goal:** Change the state of the qubits to $\\frac{1}{2} \\big(|00\\rangle + i|01\\rangle - |10\\rangle - i|11\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We will start approaching the problem from the desired end result. Let’s see if we can factor any expressions out of $\\big(|00\\rangle + i|01\\rangle - |10\\rangle - i|11\\rangle\\big)$:\n",
    "\n",
    "\\begin{equation}\n",
    "|00\\rangle + i|01\\rangle - |10\\rangle - i|11\\rangle\n",
    "= |00\\rangle + \\big(|0\\rangle - |1\\rangle\\big) i|1\\rangle - |10\\rangle = \\\\\n",
    "= \\big(|0\\rangle - |1\\rangle\\big) |0\\rangle + \\big(|0\\rangle - |1\\rangle\\big) i|1\\rangle\n",
    "= \\big(|0\\rangle - |1\\rangle\\big) \\otimes \\big(|0\\rangle + i|1\\rangle\\big)\n",
    "\\label{5.1} \\tag{5.1}\n",
    "\\end{equation}\n",
    "\n",
    "The fact that we were able to factor out the state into a tensor product of two terms means the state is separable.\n",
    "\n",
    "This is looking promising.  Now let’s try to approach the problem from the other end, i.e. from the starting state of $|00\\rangle$. \n",
    "As we've seen in the previous task, applying a Hadamard operation to each $|0\\rangle$ gets us closer to the factored-out expression:\n",
    "\n",
    "\\begin{equation}\n",
    "H|0\\rangle \\otimes H|0\\rangle = \\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big) \\otimes \\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big)\n",
    "=\\frac{1}{2} \\big(|0\\rangle + |1\\rangle\\big) \\otimes \\big(|0\\rangle + |1\\rangle\\big) \n",
    "\\label{5.2} \\tag{5.2}\n",
    "\\end{equation}\n",
    "\n",
    "If we compare equations 5.1 and 5.2 (while ignoring the $\\frac{1}{2}$ term in equation 5.2), we end up with the following transformations that we need to perform on the individual qubits:\n",
    "\n",
    "\\begin{equation}\n",
    "|0\\rangle + |1\\rangle \\overset{???}\\rightarrow |0\\rangle - |1\\rangle\n",
    "\\label{5.3} \\tag{5.3}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "|0\\rangle + |1\\rangle \\overset{???}\\rightarrow |0\\rangle + i|1\\rangle\n",
    "\\label{5.4} \\tag{5.4}\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "Next lets take a look at our basic gates, in particular the <a href=\"https://en.wikipedia.org/wiki/Quantum_logic_gate#Pauli-Z_(%7F'%22%60UNIQ--postMath-00000021-QINU%60%22'%7F)_gate\">Pauli Z gate</a>:\n",
    "\n",
    "$$Z = \\begin{bmatrix} 1 & 0 \\\\ 0 & -1 \\end{bmatrix}$$\n",
    "\n",
    "If it is applied to the state $\\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big)$, it will leave the basis state $|0\\rangle$ unchanged and will map $|1\\rangle$ to $-|1\\rangle$. Thus, \n",
    "\n",
    "$$Z\\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big) = \\frac{1}{\\sqrt2} \\big(|0\\rangle - |1\\rangle\\big)$$\n",
    "\n",
    "So the Z gate is the answers to the question of how to do the conversion 5.3. \n",
    "\n",
    "Looking for another gate to address the conversion 5.4, we find the <a href=\"https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.s\">S gate</a>:\n",
    "\n",
    "$$S = \\begin{bmatrix} 1 & 0 \\\\ 0 & i \\end{bmatrix}$$ \n",
    "\n",
    "If it is applied to the state $\\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big)$, it will leave the basis state $|0\\rangle$ unchanged and will map $|1\\rangle$ to $i|1\\rangle$. Thus, \n",
    "\n",
    "$$S\\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big) = \\frac{1}{\\sqrt2} \\big(|0\\rangle + i|1\\rangle\\big)$$\n",
    "\n",
    "So the S gate now answers the question of how to do the conversion 5.4.\n",
    "\n",
    "To summarize, the state we need to prepare can be represented as follows:\n",
    "$$ZH|0\\rangle \\otimes SH|0\\rangle$$\n",
    "\n",
    "Remember that in Q# the gates have to be applied in reverse order compared to the mathematical notation - the gate closest to the ket symbol is applied first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T05_AllBasisVectorsWithPhases_TwoQubits_Test\n",
    "\n",
    "operation AllBasisVectorsWithPhases_TwoQubits (qs : Qubit[]) : Unit {\n",
    "    H(qs[0]);\n",
    "    Z(qs[0]);\n",
    "\n",
    "    H(qs[1]);\n",
    "    S(qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 5 of the Superposition kata.](./Superposition.ipynb#superposition-of-basis-vectors-with-phases)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"bell-state\"></a> Task 6. Bell state $|\\Phi^{+}\\rangle$.\n",
    "\n",
    "**Input:** Two qubits in the $|00\\rangle$ state (stored in an array of length 2).\n",
    "\n",
    "**Goal:**  Change the state of the qubits to $|\\Phi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|00\\rangle + |11\\rangle\\big)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "The first thing we notice is that, unlike in the previous task, we cannot represent this state as a tensor product of two individual qubit states - this goal state is NOT separable. \n",
    "\n",
    "> How can we see this? Let's assume that this state can be represented as a tensor product of two qubit states: \n",
    ">\n",
    "> $$|\\psi_1\\rangle \\otimes |\\psi_2\\rangle = (\\alpha_1|0\\rangle + \\beta_1|1\\rangle) \\otimes (\\alpha_2|0\\rangle + \\beta_2|1\\rangle) = \\alpha_1\\alpha_2|00\\rangle + \\alpha_1\\beta_2|01\\rangle + \\beta_1\\alpha_2|10\\rangle + \\beta_1\\beta_2|11\\rangle$$ \n",
    ">\n",
    ">In order for this state to be equal to $\\frac{1}{\\sqrt2}\\big(|00\\rangle + |11\\rangle\\big)$, we need to have $\\alpha_1\\alpha_2 = \\beta_1\\beta_2 = \\frac{1}{\\sqrt2}$ and at the same time $\\alpha_1\\beta_2 = \\beta_1\\alpha_2 = 0$, which is impossible.\n",
    ">\n",
    ">This is the first time we encounter the phenomena called **entanglement**, in which the states of the qubits are linked together and can not be considered individually.  \n",
    "\n",
    "Let's see what steps we can take to prepare this state without factoring it into states of individual qubits.\n",
    "\n",
    "---\n",
    "\n",
    "First, we notice that we should end with a superposition of two of the four computational basis for two qubits: $|00\\rangle, |01\\rangle, |10\\rangle, |11\\rangle$.\n",
    "\n",
    "This gives us a hint that we should start by preparing a superposition on at least one of the qubits. Let’s try creating a superposition on the first qubit with a Hadamard gate: \n",
    "\n",
    "$$H|0\\rangle \\otimes |0\\rangle = \\frac{1}{\\sqrt2} (|0\\rangle + |1\\rangle) \\otimes |0\\rangle = \\frac{1}{\\sqrt2} (|00\\rangle + |10\\rangle)$$\n",
    "\n",
    "Well, we got pretty close, except we need to transform the $|10\\rangle$ state to $|11\\rangle$.\n",
    "How can we do this? \n",
    "\n",
    "We can take advantage of controlled gates, specifically the [controlled NOT gate](https://en.wikipedia.org/wiki/Controlled_NOT_gate), also referred to as CNOT. This gate acts on two qubits, hence it is represented as a $4 \\times 4$ unitary matrix. The CNOT gate changes the target qubit from state $|0\\rangle$ to $|1\\rangle$ and vice versa when the control qubit is $|1\\rangle$ and does nothing to the target qubit when the control qubit is $|0\\rangle$. The control qubit always remains unchanged. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table style=\"background-color: white; border:1px solid; tr  { background-color:transparent; }\">\n",
    "    <col width=300>\n",
    "    <col width=300>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Matrix</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Circuit</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\">$\\text{CNOT} = \\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix}$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/CNOTGateCircuit.png\"/></td>    \n",
    "      </tr>      \n",
    "</table> <br>\n",
    "<center>The matrix and circuit representation of CNOT</center><br>\n",
    "\n",
    "If we apply the CNOT gate to the state $\\frac{1}{\\sqrt2} (|00\\rangle + |10\\rangle)$, taking the first qubit as the control and the second one as target, we'll get exactly the desired goal state. \n",
    "<img src=\"./img/Task6OutputHadamardasControl.png\" width=\"200\"/>\n",
    " \n",
    "<table style=\"background-color: white; border:1px solid; tr  { background-color:transparent; }\">\n",
    "    <col width=500>\n",
    "    <col width=300>\n",
    "    <col width=300>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Steps required to reach goal state</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Notation</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Circuit</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:left; border:1px solid\">1. Apply a Hadamard gate to the first qubit. <br/> 2. Applying a CNOT with first qubit as control and second qubit as target.</td>\n",
    "        <td style=\"text-align:center; border:1px solid; font-bold; font-size: 16px; \">$\\frac{1}{\\sqrt2} (|00\\rangle + |11\\rangle)$</td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/Task6HadamardCNOTCircuit.png\"/></td>\n",
    "      </tr>      \n",
    "</table>\n",
    "\n",
    "In matrix representation we can represent this operation as a product of two $4 \\times 4$ matrices, with the matrix corresponding to the first step being the tensor product of a Hadamard gate on the first qubit and identity gate on the second qubit.\n",
    "\n",
    "$$H \\otimes I = \\frac{1}{\\sqrt2} \\begin{bmatrix} 1 & 1  \\\\ 1 & -1 \\end{bmatrix} \\otimes \\begin{bmatrix} 1 & 0  \\\\ 0 & 1 \\end{bmatrix} = \n",
    "\\frac{1}{\\sqrt2}\\begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 1 & 0 & -1 & 0 \\\\ 0 & 1 & 0 & -1 \\end{bmatrix}$$\n",
    "\n",
    "$$\\underset{\\text{CNOT}}{\\underbrace{\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix}}} \n",
    "\\cdot \n",
    "\\underset{H \\otimes I}{\\underbrace{\\frac{1}{\\sqrt2} \\begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 1 & 0 & -1 & 0 \\\\ 0 & 1 & 0 & -1 \\end{bmatrix}}}\n",
    "\\cdot\n",
    "\\underset{|0\\rangle}{\\underbrace{ \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix}}}\n",
    "= \\frac{1}{\\sqrt2} \\begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 0 & 1 & 0 & -1 \\\\ 1 & 0 & -1 & 0 \\end{bmatrix}\n",
    "\\cdot\n",
    "\\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\end{bmatrix}\n",
    "= \\underset{goal}{\\underbrace{ \\frac{1}{\\sqrt2} \\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 1 \\end{bmatrix}}}\n",
    "\\label{6.1} \\tag{6.1}\n",
    "$$\n",
    "\n",
    "Note that in the matrix representation and in Dirac notation the gates are applied from right to left (the rightmost operation happens firts), while in circuit notation the operations are applied from left to right (the leftmost operation happens first)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T06_BellState_Test\n",
    "\n",
    "operation BellState (qs : Qubit[]) : Unit {\n",
    "    H(qs[0]);\n",
    "    CNOT(qs[0], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 6 of the Superposition kata.](./Superposition.ipynb#bell-state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <a name=\"all-bell-states\"></a> Task 7. All Bell states.\n",
    "\n",
    "**Inputs:** \n",
    "\n",
    "1. Two qubits in the $|00\\rangle$ state (stored in an array of length 2).\n",
    "2. An integer `index`.\n",
    "\n",
    "**Goal:**  Change the state of the qubits to one of the Bell states, based on the value of index:\n",
    "\n",
    "<table>\n",
    "  <col width=\"50\"/>\n",
    "  <col width=\"200\"/>\n",
    "  <tr>\n",
    "    <th style=\"text-align:center\">Index</th>\n",
    "    <th style=\"text-align:center\">State</th>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">0</td>\n",
    "    <td style=\"text-align:center\">$|\\Phi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|00\\rangle + |11\\rangle\\big)$</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">1</td>\n",
    "    <td style=\"text-align:center\">$|\\Phi^{-}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|00\\rangle - |11\\rangle\\big)$</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">2</td>\n",
    "    <td style=\"text-align:center\">$|\\Psi^{+}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|01\\rangle + |10\\rangle\\big)$</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td style=\"text-align:center\">3</td>\n",
    "    <td style=\"text-align:center\">$|\\Psi^{-}\\rangle = \\frac{1}{\\sqrt{2}} \\big (|01\\rangle - |10\\rangle\\big)$</td>\n",
    "  </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solutions\n",
    "\n",
    "> The [Bell states](https://en.wikipedia.org/wiki/Bell_state) form an orthonormal basis in the 4-dimensional space that describes the states of a 2-qubit system. \n",
    "You can check that the norm of each of these states is 1, and their inner product of each pair of states is 0.\n",
    "\n",
    "The goal is to transform the $|00\\rangle$ basis state into one of the Bell basis states, depending on the value of `index` given as an input.\n",
    "\n",
    "We will describe two solutions, one of which will be based on the previous task, and the second one will help us understand the unitary transformation that converts the computational basis into the Bell basis.\n",
    "\n",
    "#### Solution 1\n",
    "\n",
    "Let's use the first Bell state we prepared in the previous task and transform it according to the value of `index`.\n",
    "\n",
    "<table>\n",
    "    <col width=300>\n",
    "    <col width=50>\n",
    "    <col width=300>\n",
    "    <tr bgcolor=\"white\">\n",
    "        <td bgcolor=\"white\" style=\"text-align:center\"><img src=\"./img/Task6HadamardCNOTCircuit.png\"/></td>\n",
    "        <td bgcolor=\"white\" style=\"text-align:center;font-size: 30px\">$\\Longrightarrow$</td>\n",
    "        <td bgcolor=\"white\" style=\"text-align:center;font-size: 20px\">$\\frac{1}{\\sqrt2} \\big(|00\\rangle + |11\\rangle\\big)$</td>\n",
    "      </tr>      \n",
    "</table>\n",
    "\n",
    "What transformation do we need to apply to get to the final state?\n",
    "\n",
    "* If `index = 0`, we do nothing - the prepared state is already $|\\Phi^{+}\\rangle$.\n",
    "\n",
    "* If `index = 1`, we need to add a relative phase of $-1$ to the $|11\\rangle$ term. Remember that Z gate does exactly that with a qubit:\n",
    "  \n",
    "  $$Z(H|0\\rangle) \\otimes |0\\rangle = \\frac{1}{\\sqrt2} \\big(|0\\rangle - |1\\rangle\\big) \\otimes |0\\rangle = \\frac{1}{\\sqrt2} \\big(|00\\rangle - |10\\rangle\\big)$$\n",
    "  \n",
    "  If we now apply the CNOT as before, we will have:\n",
    "\n",
    "  $$\\frac{1}{\\sqrt2} \\big(|00\\rangle - |\\overset{\\curvearrowright}{10}\\rangle\\big) \\underset{\\text{CNOT}}{\\Longrightarrow} \\frac{1}{\\sqrt2} \\big(|00\\rangle - |11\\rangle\\big) = |\\Phi^{-}\\rangle$$\n",
    "\n",
    "* If `index = 2`, we need to change the second qubit in both $|00\\rangle$ and $|11\\rangle$ terms, which can be done applying an X gate:\n",
    "  \n",
    "  $$H|0\\rangle \\otimes X|0\\rangle = H|0\\rangle \\otimes |1\\rangle = \\frac{1}{\\sqrt2} \\big(|0\\rangle + |1\\rangle\\big) \\otimes |1\\rangle = \\frac{1}{\\sqrt2} \\big(|01\\rangle + |11\\rangle\\big)$$\n",
    "  \n",
    "  If we now apply the CNOT as before, we will have:\n",
    "  \n",
    "  $$\\frac{1}{\\sqrt2} \\big(|01\\rangle + |\\overset{\\curvearrowright}{11}\\rangle\\big) \\underset{\\text{CNOT}}{\\Longrightarrow} \\frac{1}{\\sqrt2} \\big(|01\\rangle + |10\\rangle\\big) = |\\Psi^{+}\\rangle$$\n",
    "\n",
    "* If `index = 3`, we use the same logic to realize that we need to apply both the Z and X corrections to get $|\\Psi^{-}\\rangle$ state.\n",
    "\n",
    "The final sequence of steps is as follows:\n",
    "1. Apply the H gate to the first qubit. \n",
    "2. Apply the Z gate to the first qubit if `index = 1` or `index == 3`.\n",
    "3. Apply the X gate to the second qubit if `index = 2` or `index == 3`.\n",
    "4. Apply the CNOT gate with the first qubit as control and the second qubit as target.\n",
    "\n",
    "<table style=\"background-color: white; border:1px solid; tr  { background-color:transparent; }\">\n",
    "    <col width=200>\n",
    "    <col width=200>\n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Index 0</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Index 1</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/Task7.Index0.png\"/></td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/Task7.Index1.png\"/></td>    \n",
    "     </tr>        \n",
    "    <tr>\n",
    "        <th style=\"text-align:center; border:1px solid\">Index 2</th>\n",
    "        <th style=\"text-align:center; border:1px solid\">Index 3</th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/Task7.Index2.png\"/></td>\n",
    "        <td style=\"text-align:center; border:1px solid\"><img src=\"./img/Task7.Index3.png\"/></td>    \n",
    "     </tr>      \n",
    "</table>\n",
    "<center>Circuits to be applied to prepare the four Bell States</center>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T07_AllBellStates_Test\n",
    "\n",
    "operation AllBellStates (qs : Qubit[], index : Int) : Unit {\n",
    "    H(qs[0]);\n",
    "    \n",
    "    if (index == 1) {\n",
    "        Z(qs[0]);\n",
    "    }\n",
    "    if (index == 2) {\n",
    "        X(qs[1]);\n",
    "    }\n",
    "    if (index == 3) {\n",
    "        Z(qs[0]);\n",
    "        X(qs[1]);\n",
    "    }\n",
    "    \n",
    "    CNOT(qs[0], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution 2\n",
    "\n",
    "Let's take a closer look at the unitary transformation $\\text{CNOT}\\cdot(H \\otimes I)$ discussed in task 6 (see equation 6.1).\n",
    "\n",
    "<table>\n",
    "    <col width=300>\n",
    "    <col width=50>\n",
    "    <col width=300>\n",
    "    <tr bgcolor=\"white\">\n",
    "        <td bgcolor=\"#FFFFFF\" style=\"text-align:center\"><img src=\"./img/Task6HadamardCNOTCircuit.PNG\"/></td>\n",
    "        <td bgcolor=\"#FFFFFF\" style=\"text-align:center;font-size: 30px\">$\\Leftrightarrow$</td>\n",
    "        <td bgcolor=\"#FFFFFF\" style=\"text-align:center;font-size: 20px\">$\\frac{1}{\\sqrt2} \\begin{bmatrix} 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 0 & 1 & 0 & -1 \\\\ \\underset{|\\Phi^{+}\\rangle}{\\underbrace{1}} & \\underset{|\\Psi^{+}\\rangle}{\\underbrace{0}} & \\underset{|\\Phi^{-}\\rangle}{\\underbrace{-1}} & \\underset{|\\Psi^{-}\\rangle}{\\underbrace{0}} \\end{bmatrix}$</td>\n",
    "      </tr>      \n",
    "</table>\n",
    "\n",
    "Notice that each of the columns in the unitary matrix corresponds to one of the Bell States.\n",
    "This unitary transformation transforms the computational basis into the Bell basis, which is exactly what the task asks us to do.\n",
    "\n",
    "We see that this transformation converts $|00\\rangle$ into the first Bell state, $|01\\rangle$ into the second Bell state, etc. \n",
    "We just need to make sure we set the qubits to the correct state before applying this transformation, using X gates to change the initial $|0\\rangle$ states to $|1\\rangle$ if needed. \n",
    "\n",
    "In Q#, we can use the <a href=\"https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.convert.intasboolarray\">IntAsBoolArray</a> function to convert the input `index` to the right bit pattern."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%kata T07_AllBellStates_Test\n",
    "   \n",
    "open Microsoft.Quantum.Convert;\n",
    "\n",
    "operation AllBellStates (qs : Qubit[], index : Int) : Unit {\n",
    "    let bitmask = IntAsBoolArray(index, 2);\n",
    "    \n",
    "    if (bitmask[0]) {\n",
    "        X(qs[0]);\n",
    "    }\n",
    "\n",
    "    if (bitmask[1]) {\n",
    "        X(qs[1]);\n",
    "    }\n",
    "\n",
    "    H(qs[0]);\n",
    "    CNOT(qs[0], qs[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Return to task 7 of the Superposition kata.](./Superposition.ipynb#all-bell-states)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solutions to the rest of the tasks are included in the [Superposition Kata Workbook, Part 2](./Workbook_Superposition_Part2.ipynb)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
